It is very common to add indexes to data to rapidly search a large amount of data for a small amount of data. As the target for which the searching process is frequently performed, databases are used. Of the databases, a relational database that manages data in a tabular form is the most widely used. A table is formed by rows and columns, and for example, one row contains data concerning one transaction. The row is formed by plural columns, and for example, a certain column contains date data, while another column contains a sales amount.
In this case, the total sale amount at a specific date can be obtained, for example, through full scan or index scan. In the full scan, examination for all the rows is made as to whether the dates are matched or not, and the sales amounts in the matched rows are added up. In the index scan, the rows having the date matched with each other are specified using indexes, whereby the total of the sales amount can be obtained from the specified rows. This index scan is efficient when the number of rows having the date matched is sufficiently small as compared with the number of all the rows.
A B-tree is known as a data structure that accommodates the indexes. For example, Non-patent Document 1 describes algorithms including searching with the B-tree, inserting of data into the B-tree, and deleting data in the B-tree. Non-patent Document 2 makes an explanation of the B-tree in ORACLE (trademark) in relation to the widely used relational database.
With the B-tree index, it is possible to search for the data with the calculation amount in proportion to “log n”, where n is the number of rows. Note that the amount of calculation in the full scan is proportion to the n.